import java.util.ArrayList;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-06
 * Time: 11:57
 */
//最理想的办法是使用快排，对数组进行排序之后，取前k个数字加入到结果集中即可；
public class Solution2 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if ( k == 0 ) {
            return result;
        }
        if ( input.length == 0 ) {
            return result;
        }
        quickSort( input , 0 , input.length - 1 );
        for (int i = 0; i < k; i++) {
            result.add( input[i] );
        }
        return result;
    }
    //快排，交换法
    private void quickSort(int[] input,int start,int end){
        if(start>=end){
            return;
        }
        int left=start;
        int right=end;
        //去一个基准值
        int pivot=input[(left+right)/2];
        while(left<=right){
            //等到两边都不符合要求了，那么就交换左右两边的值
            while(left<=right && input[left]<pivot){
                left++;
            }
            while ( left <= right && input[right]>pivot ) {
                right--;
            }
            if(left<=right){
                int temp=input[left];
                input[left]=input[right];
                input[right]=temp;
                left++;
                right--;
            }
        }
        //left>right，也就是部分的已经有序，递归排序缩短范围，继续排序
        quickSort(input,start,right);
        quickSort(input,left,end);
    }
}
